/**
 * 面试题14-2：剪绳子II
 */
public class Offer_14_II {
    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        long ans = 1;
        while (n > 4) {
            n -= 3;
            ans *= 3;
            ans %= 1000000007;
        }
        return (int) (n * ans % 1000000007);
    }

    public static void main(String[] args) {
        Offer_14_II solution = new Offer_14_II();
        int ans = solution.cuttingRope(120);
        System.out.println(ans);
    }
}
